//
//  backData.swift
//  PlayData
//
//  Created by 冯琰琰 on 2022/4/9.
//

import Foundation

class SolutionBack {
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
        var value1 = 0
        var value2 = 0
        for i in 0..<nums.count {
            for j in (i+1)..<nums.count {
                if (nums[i] + nums[j] == target) {
                    value1 = i
                    value2 = j
                    break
                }
            }
        }
        if value1 == 0 && value2 == 0 {
            return []
        }
        return [value1,value2]
    }
    
    
    func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
        var h1 = l1
        var h2 = l2
        
        var arr1 = [Int]()
        var arr2 = [Int]()
        
        var res = ListNode()
        let head = res
        while h1 != nil {
            arr1.append(h1!.val)
            h1 = h1?.next
        }
        
        while h2 != nil {
            arr2.append(h2!.val)
            h2 = h2?.next
        }
        
        var carry = 0 // 进位
        
        let arrres = arr1.count > arr2.count ? arr1 : arr2
        
        for i in 0..<arrres.count {
            
            let value1 = arr1.count > i ? arr1[i] : 0
            let value2 = arr2.count > i ? arr2[i] : 0
            
            var value = value1 + value2 + carry
            carry = value / 10
            value = value % 10
            
            let tempRes = ListNode()
            tempRes.val = value
            res.next = tempRes
            res = tempRes
            
        }
        
        if carry > 0 {
            let tempRes = ListNode()
            tempRes.val = carry
            res.next = tempRes
        }
        return head.next
    }
    
    func lengthOfLongestSubstring(_ s: String) -> Int {
        if s.isEmpty {
            return 0
        }
        let characters = Array(s).map { String($0) }
        var sArr = [String]()
        var max = 1
        for i in 0..<characters.count {
            sArr.removeAll()
            sArr.append(characters[i])
            for j in (i+1)..<characters.count {
                if sArr.contains(characters[j]) {
                    break
                } else {
                    sArr.append(characters[j])
                }
                if sArr.count > max {
                    max = sArr.count
                }
            }
        }
        return max
    }
    
    func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {
        var header:ListNode? = ListNode()
        header?.next = head
        
        var h1 = header
        var h2 = header
        var res = h1
        var index = 0
        while h2 != nil {
            h2 = h2?.next
            index = index + 1
            if index > n && h2 != nil {
                h1 = h1?.next
            }
        }
        h1?.next = h1?.next?.next
        return res?.next
    }
    
    // 滑动窗口方案
    func lengthOfLongestSubstring2(_ s: String) -> Int {
        let arr = s.map{String($0)}
        var start = 0
        var end = 0
        var map = [String : Int]()
        var maxV = 0
        while end < arr.count {
            let str = arr[end]
            if map.keys.contains(str) {
                start = max(map[str]!, start)
            }
            
            map[str] = end + 1
            maxV = max(maxV, end - start + 1)
            end += 1
        }
        return maxV
    }
    
    func reverse(_ x: Int) -> Int {
        var val = x
        var result = 0
        while val > 0 {
            let s = val % 10
            val = val / 10
            result = result * 10 + s
            
            if result > Int.max || result < Int.min {
                return 0
            }
        }
        return result
    }
    
    func removeNthFromEnd2(_ head: ListNode?, _ n: Int) -> ListNode? {
        
        let node:ListNode? = ListNode()
        node?.next = head
        
        var fast = node
        var slow = node
        var index = 0
        let result = slow
        while fast?.next != nil {
            fast = fast?.next
            if index >= n {
                slow = slow?.next
            }
            index += 1
        }
        
        slow?.next = slow?.next?.next
        
        return result?.next
    }
    
    func isValid(_ s: String) -> Bool {
        let map = ["(":")","[":"]","{":"}"]
        
        let sArr = s.map{String($0)}
        
        
        var stack = [String]()
        for str in sArr {
            if map.keys.contains(str) {
                stack.append(str)
            } else {
                let first = stack.last
                if first == nil || map[first!] != str {
                    return false
                }
                stack.removeLast()
            }
            
        }
        return stack.isEmpty
    }
    
    
    func rotateRight(_ head: ListNode?, _ k: Int) -> ListNode? {
        var tail = head
        var result = tail
        var num = 1
        while tail?.next != nil {
            tail = tail?.next
            num += 1
        }
        tail?.next = result
        
        var amount = k - num % k - 1
        while amount > 0 {
            result = result?.next
            amount -= 1
        }
        let val = result?.next
        result?.next = nil
        return val

    }
    
    func reverseBetween(_ head: ListNode?, _ left: Int, _ right: Int) -> ListNode? {
        
        let node:ListNode? = ListNode()
        node?.next = head
        
        
        var preStart = node
        let val = preStart
        
        for _ in 0 ..< left-1 {
            preStart = preStart?.next
        }
        
        let start = preStart?.next
        var end = start
        for _ in 0..<right-left {
            end = end?.next
        }
        
        let endnext = end?.next
        end?.next = nil
        let result = reverseList(start)
        
        preStart?.next = result
        start?.next = endnext
        
        return val

    }
    
    func reverseList(_ head: ListNode?) -> ListNode? {
        var cur = head
        var pre:ListNode? = nil
        while cur != nil {
            let node = cur?.next
            cur?.next = pre
            pre = cur
            cur = node
        }
        return pre
    }
    
    
    var resultTree = [Int]()
    func inorderTraversal(_ root: TreeNode?) -> [Int] {
        inTra(root)
        return resultTree

    }
    
    func inTra(_ root: TreeNode?) {
        if root == nil {
            return
        }
        inTra(root?.left)
        resultTree.append(root!.val)
        inTra(root?.right)
    }
    
    func isSymmetric(_ root: TreeNode?) -> Bool {
        return isSymmetrics(root?.left, root?.right)
    }
    
    func isSymmetrics(_ left: TreeNode?,_ right: TreeNode?) -> Bool {
        if left == nil && right == nil {
            return true
        }
        if left?.val != right?.val || left?.left?.val != right?.right?.val || left?.right?.val != right?.left?.val {
            return false
        }
        return isSymmetrics(left?.left, right?.right) && isSymmetrics(left?.right, right?.left)
    }
    
    
    
    func levelOrder(_ root: TreeNode?) -> [[Int]] {
        var res = Array<[Int]>()
        if root == nil {
            return res
        }
        var stack = [TreeNode]()
        stack.append(root!)
        while !stack.isEmpty {
            var resSub = [Int]()
            for _ in 0..<stack.count {
                let node = stack.removeFirst()
                resSub.append(node.val)
                
                if node.left != nil {
                    stack.append(node.left!)
                }
                if node.right != nil {
                    stack.append(node.right!)
                }
            }
            res.append(resSub)
        }
        return res
    }
    
    func maxDepth(_ root: TreeNode?) -> Int {
        if root?.left == nil && root?.right == nil {
            return 1
        }
        return min(maxDepth(root?.left), maxDepth(root?.right)) + 1
    }
    func minDepth(_ root: TreeNode?) -> Int {
        if root == nil {
            return 0
        }
        let left = minDepth(root?.left)
        let right = minDepth(root?.right)
        
        if root?.left == nil || root?.right == nil {
            return 1
        } else {
            return min(left, right) + 1
        }
    }
    
    func getMid(_ left: ListNode?,_ right: ListNode?) -> ListNode? {
        var slow = left
        var fast = left
        while fast !== right && fast?.next !== right {
            fast = fast?.next?.next
            slow = slow?.next
        }
        return slow
    }
    
    func buildTree(_ left: ListNode?,_ right: ListNode?) -> TreeNode? {
        if left === right {
            return nil
        }
        let mid = getMid(left, right)
        
        let midNoed = TreeNode(mid!.val)
        midNoed.left = buildTree(left,mid)
        midNoed.right = buildTree(mid, right)
        return midNoed
    }
    
    func sortedListToBST(_ head: ListNode?) -> TreeNode? {
        return buildTree(head,nil)
    }
    
    
    func isBalanced(_ root: TreeNode?) -> Bool {
        if root == nil {
            return true
        }
        let left = getHeight(root?.left)
        let right = getHeight(root?.right)
        return abs(left - right) < 2 && isBalanced(root?.left) && isBalanced(root?.right)
    }
    
    func getHeight(_ root: TreeNode?) -> Int{
        if root == nil {
            return 0
        }
        return max(getHeight(root?.left), getHeight(root?.right)) + 1
    }
    
}

